Mountain climbing problem

In mathematics, the mountain climbing problem is a problem of finding conditions two function forming profiles of a two-dimensional mountain must satisfy, so that two climbers can start on the bottom on the opposite sides of the mountain and coordinate their movements to reach to the top while always staying at the same height. This problem was named and posed in this form by James V. Whittaker in 1966, but its history goes back to Tatsuo Homma, who solved a version of it in 1952. The problem has been repeatedly rediscovered and solved independently in different context by a number of people (see the references).

In the past two decades the problem was shown to be connected to the weak Fréchet distance of curves in the plane (see Buchin et al.), various planar motion planning problems in computational geometry (see Goodman et al.), the square peg problem (see Pak), semigroup of polynomials (see Baird and Magill), etc. The problem was popularized in the article by Goodman et al., which received the MAA writing award in 1990.

Contents

Understanding the problem

It is easy to coordinate the climbers' movement between the peaks and valleys (local maxima and minima of the functions). The difficulty is that to progress, the climbers must occasionally go down the mountain, either one or the other, or both climbers. Similarly, either one or the other climber must backtrack towards the beginning of the journey. In fact, it has been observed that for a mountain with n peaks and valleys the number of turns can be as large as quadratic in n (see Buchin et al.). These difficulties make the problem unintuitive and sometimes rather difficult, both in theory and in practice.

Formulation

The following result is due to Huneke:

Suppose f and g are continuous functions from [0,1] to [0,1] with f(0)=g(0)=0 and f(1)=g(1)=1, and such that neither function is constant on an interval. Then there exist continuous functions s and t from [0,1] to [0,1] with s(0)=t(0)=0, s(1)=t(1)=1, and such that f\circ s \, = \, g\circ t, where "\circ" stands for a composition of functions.

To see heuristically that the result does not extend to all continuous functions, note that if f has a constant interval while g has a highly oscillating interval on the same level, then the first climber would be forced to go back and forth infinitely many times, and thus can never reach the top.

It is also known that for the piecewise linear functions there are no obstructions, i.e. the climbers can always coordinate their movements to get to the top (see Whittaker).

Proof in the piecewise linear case

Consider a graph G of all positions on a mountain both climbers can occupy on the same level. This graph is piecewise linear, i.e. a union of intervals, and can be viewed as a graph in Graph theory. Note that G may or may not be connected. The vertices of the intervals correspond to peaks and valleys of the functions. There are three cases:

1. One climber is at a peak or a valley, another climber is in between two of them,
2. Both climbers are at a peak or at valley.
3. One climber is at a peak and one is at valley.

In the first case such vertex of G has two adjacent intervals, in the second case it has four, and in the last case zero. Therefore, graph G has all vertices of even degree, except for the point (0,0) corresponding to two climbers on the bottom and the point (1,1) corresponding to two climbers on top of the mountain. Applying the handshaking lemma to the connected component of G containing (0,0) we conclude that (0,0) and (1,1) are in the same connected component of G. This implies that there is a path from (0,0) to (1,1) in G. In the language of mountain climbers, this gives a way to coordinate the climbers' movement to reach the top of the mountain.

References

External links